#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef int binary_tree_data_type;
typedef struct binary_tree_node
{
	char data;
	binary_tree_node* left;
	binary_tree_node* right;
} node;

//construct the tree by string

node* create_node(char ch)
{
	node* newnode = (node*)malloc(sizeof(node));
	if (!newnode)
		exit(1);

	newnode->data = ch;
	newnode->left = nullptr;
	newnode->right = nullptr;
	return newnode;
}
void create_tree(node*& root, const string& str, int& i)
{
	if (i == str.size())
		return;
	if (str[i] == '$')
	{
		++i;
		root = nullptr;
		return;
	}
	root = create_node(str[i++]);
	create_tree(root->left, str, i);
	create_tree(root->right, str, i);
}
void preorder_traversal(node* root)
{
	if (root == nullptr)
		return;
	cout << root->data << " ";
	preorder_traversal(root->left);
	preorder_traversal(root->right);
}
void postorder_traversal(node* root)
{
	if (root == nullptr)
		return;
	postorder_traversal(root->left);
	postorder_traversal(root->right);
	cout << root->data << " ";
}
void inorder_traversal_by_stack(node* root)
{
	stack<node*> st;
	 vector<binary_tree_data_type> v;
	node* cur = root;
	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->left;
		}
		//get top
		node* top = st.top();
		st.pop();
		cout << top->data << " ";
		 v.push_back(top->data);
		cur = top->right;
	}
}
void level_traversal(node* root)
{
	queue<node*> q;
	q.push(root);
	while (!q.empty())
	{
		node* front = q.front();
		q.pop();
		cout << front->data << " ";

		if (front->left)
			q.push(front->left);
		if (front->right)
			q.push(front->right);
	}
}
void inorder_traversal(node* root)
{
	node* cur = root;
	while (cur)
	{
		if (cur->left == nullptr)
		{
			cout << cur->data << " "; // most left node
			cur = cur->right;         //  next right tree
		}
		else
		{
			 //find the most right node in the left tree of the current node
			node* prev = cur->left;
			// two factor may be the reason break the while loop
			while (prev->right != nullptr && prev->right != cur)
			{
				prev = prev->right;
			}
			// has not visit the cur`s left
			if (prev->right == nullptr)
			{
				prev->right = cur;
				cur = cur->left; // then continue visit the left
			}
			else // has visited the cur`s left
			{
				cout << cur->data << " ";
				prev->right = nullptr; // cut the link
				cur = cur->right;
			}
		}
	}
}
int height(node* root)
{
	if (root == nullptr)
		return 0;
	return 1 + max(height(root->left), height(root->right));
}
void menu()
{
	cout << "|-------------------------------------|" << endl;
	cout << "|       1. create_binary_tree         |" << endl;
	cout << "|       2. preorder_traversal         |" << endl;
	cout << "|       3. inorder_traversal_1        |" << endl;
	cout << "|       4. inorder_traversal_2        |" << endl;
	cout << "|       5. postorder_traversal        |" << endl;
	cout << "|       6. level_traversal            |" << endl;
	cout << "|       7. height                     |" << endl;
	cout << "|       0. exit                       |" << endl;
	cout << "|-------------------------------------|" << endl;

}
int main()
{
	int input;
	node* root = nullptr;
	bool is_created = false;
	do
	{
		menu();
		cout << "option:> ";
		cin >> input;
		switch (input)
		{
		case 0:
			cout << "already exited" << endl;
			break;
		case 1:
		{
			cout << "enter a string to be transformed as a tree:> " ;
			string str = "ABC$$DE$G$$F$$$";
			cin >> str;
			int i = 0;
			create_tree(root, str, i);

			cout << "the tree was created" << endl;
			is_created = true;
			break;
		}
		case 2:
			if (is_created == false)
			{
				cout << "please create the tree first!!" << endl;
				break;
			}
			cout << "preorder_traversal: ";
			preorder_traversal(root);
			cout << endl;
			break;
		case 3:
			if (is_created == false)
			{
				cout << "please create the tree first!!" << endl;
				break;
			}
			cout << "inorder_traversal_1: ";
			inorder_traversal_by_stack(root);
			cout << endl;
			break;
		case 4:
			if (is_created == false)
			{
				cout << "please create the tree first!!" << endl;
				break;
			}
			cout << "inorder_traversal_2: ";
			inorder_traversal(root);
			cout << endl;
			break;

		case 5:
			if (is_created == false)
			{
				cout << "please create the tree first!!" << endl;
				break;
			}
			cout << "postorder_traversal: ";
			postorder_traversal(root);
			cout << endl;
			break;
		case 6:
			if (is_created == false)
			{
				cout << "please create the tree first!!" << endl;
				break;
			}
			cout << "level_traversal: ";
			level_traversal(root);
			cout << endl;
			break;
		case 7:
			if (is_created == false)
			{
				cout << "please create the tree first!!" << endl;
				break;
			}
			cout << "the height of the tree is " << height(root) << endl;
			break;
		default:
			cout << "invalid option,try again!" << endl;
			break;
		}
	} while (input);
	return 0;
}

 //int main()
 //{
 //    node *root = nullptr;
 //    string str = "ABC$$DE$G$$F$$$";
 //    int i = 0;
 //    create_tree(root, str, i);

 //    // preorder_traversal
 //    preorder_traversal(root);
 //    cout << endl;

 //    // postorder_traversal
 //    postorder_traversal(root);
 //    cout << endl;

 //    // inorder_traversal
 //    inorder_traversal(root);
 //    cout << endl;

 //    // level_traversal
 //    level_traversal(root);
 //    cout << endl;

 //    // height
 //    cout << height(root) << endl;

 //    return 0;
 //}


